There are many instances in the processing, storage, and transmission of proprietary digital, or binary, data where it is desirable for purposes of security and conservation of bandwidth to translate a series, or block, of binary data into a like ordered block of data wherein discrete bits thereof are changed to an opposite state in accordance with a reversible cryption, or transforming, procedure, encrypting the block of data. Decryption of such a block of data is achieved by application of the inverse process to that of the encryption process, reversing the bits acted upon by the encryption process back to their original state and recovering the original data. In the past, such block, or polygraphic encryption, has required a significant number of discrete operations and has been relatively slow and costly as well as fixed and limited in key size and security. In addition, block cryption schemes have typically been private key systems requiring a secure transmissions channel for distribution of the private keys. Also, these systems are generally incapable of producing digital signatures and source message authentication. Lastly, to achieve non-linear transforms, contemporary private key systems such as the ANSI Data Encryption Standard (DES), because of their complexity, generally require dedicated hardware implementations to achieve the speeds necessary to operate in-line with high speed communications channels.
Of the few public key systems that have emerged, the best known is the RSA system, disclosed in U.S. Pat. No. 4,405,829, issued in September 1983, to Rivest et al., which shows a system for encoding data as a number M in a predetermined set, raising that number to a first predetermined power, and computing the remainder when the exponentiated number is divided by the product of two predetermined prime numbers, with the remainder being the ciphertext. To decipher the ciphertext, the ciphertext is raised to a second predetermined power and the remainder computed when the exponentiated ciphertext is divided by the product of the two prime numbers, with the remainder being the original text.
Although widely used, the RSA system is slow and unwieldy, making it unsuitable for general message encryption and decryption and for inexpensive authentication devices, such as "smart card" devices, thereby limiting its use to transmission of private keys and digital signature and authentication purposes. In addition, the security of the RSA system depends on the unproved difficulty of factoring large numbers, which is threatened by ever-improving advances in factoring techniques, such as those noted in the Jun. 29, 1990, issue of Science, Vol. 238, page 1608.
Another public key system, the McEliece system as disclosed in "A Public Key Cryptosystem Based On Algebraic Coding Theory," DSN Progress Report 42-44, Jet Propulsion Laboratory, pp. 114-116, 1978, by McEliece, is workable in theory but overly complex, operates at less than fifty percent bandwidth, and has no digital signature capability. Other public key systems, such as "Knapsack Cryptosystems," disclosed in U.S. Pat. No. 4,218,582, issued on Aug. 19, 1980, to Hellman et al., and U.S. Pat. No. 4,399,323, issued on Aug. 16, 1983, to Henry, have been demonstrated to be insecure, as noted in "Breaking Iterated Knapsacks," by E. F. Brickwell, "Advances In Cryptology," proceedings of "Crypto 84," pp 51-60.
A system which is probably closest to applicants' system is system disclosed in U.S. Pat. No. 4,520,232, entitled "Polygraphic Encryption-Decryption System," to William J. Wilson (one of applicants), issued May 28, 1985. In this system, first digital memory in the encryption device is configured as a binary matrix, which is loaded with an invertible (possessing an algebraic inverse) binary matrix, this matrix forming the first of a pair of private keys. Binary data to be encrypted is "ANDed" with rows of the matrix, selecting certain rows of the matrix in accordance with the bit states of the data, and columns of selected rows are "exclusive-ORed" to produce the ciphertext. To decrypt the ciphertext, a second private key matrix which is an algebraic inverse of the first private key matrix is loaded into a second matrix-configured memory, and the ciphertext is "ANDed" with this second matrix. As with the encryption process, rows which are selected by this "ANDing" process are also "exclusive-ORed," producing the original data. While this system works relatively well, its linear cryptographic transforms are not as secure as the nonlinear transforms of the present invention. In addition, it does not provide for digital signature capabilities.
Accordingly, it is an object of this invention to provide a single, comprehensive public key cryptosystem of sufficient simplicity, speed, and security to allow the in-line performance in high-speed commercial communications and data channels of the major cryptographic transformations of encryption, decryption, and digital signature generation and for off-line creation of paired public and private keys for implementing such transformations.
Additionally, it is an object of this invention to provide a cryptosystem wherein the nonlinear cryptographic transforms effected by the public key cannot be reversed by linear algebraic transformations.
Still further, it is another object of this invention to provide random number sequences that can be verified, if necessary, in the manner of digital signatures.